#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    vector<int> tmp;
    void mergesort(vector<int>& nums, int l, int r)
    {
        if (l >= r) return;
        int mid = (r + l) >> 1;
        mergesort(nums, l, mid);
        mergesort(nums, mid + 1, r);
        int cur1 = l, cur2 = mid + 1, i = 0;
        while (cur1 <= mid && cur2 <= r)
            tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
        while (cur1 <= mid)
            tmp[i++] = nums[cur1++];
        while (cur2 <= r)
            tmp[i++] = nums[cur2++];
        for (i = l; i <= r; ++i)
            nums[i] = tmp[i - l];
    }

    vector<int> sortArray(vector<int>& nums) {
        tmp.resize(nums.size());
        mergesort(nums, 0, nums.size() - 1);
        return nums;
    }

    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n + 1);
        int mx = INT_MIN;
        for (int i = 1; i <= n; ++i)
        {
            dp[i] = max(dp[i - 1] + nums[i - 1], nums[i - 1]);
            mx = max(mx, dp[i]);
        }
        return mx;
    }

    vector<vector<int>> res;
    vector<int> path;
    void dfs(vector<int>& candidates, int target, int sum, int pos)
    {
        if (sum == target)
        {
            res.push_back(path);
            return;
        }
        if (sum > target || pos == candidates.size()) return;
        for (int i = pos; i < candidates.size(); ++i)
        {
            path.push_back(candidates[i]);
            dfs(candidates, target, sum + candidates[i], i);
            path.pop_back();
        }
    }

    void _dfs(vector<int>& candidates, int target, int sum, int pos)
    {
        if (sum == target)
        {
            res.push_back(path);
            return;
        }
        if (sum > target || pos == candidates.size()) return;
        for (int k = 0; target >= k * candidates[pos]; ++k)
        {
            if (k)path.push_back(candidates[pos]);
            dfs(candidates, target, sum + k * candidates[pos], pos + 1);
        }

        for (int k = 1; target >= k * candidates[pos]; ++k)
        {
            path.pop_back();
        }

    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        dfs(candidates, target, 0, 0);
        return res;
    }
};